#include <iostream>
#include <vector>
using namespace std;

// 二叉树节点类
class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    // 查找和为指定值的所有路径
    vector<vector<int>> findPaths(TreeNode* root, int targetSum) {
        vector<vector<int>> result;
        vector<int> currentPath;
        
        if (root == nullptr) {
            return result;
        }
        
        findPathRecursive(root, targetSum, currentPath, result);
        return result;
    }

private:
    // 递归查找路径
    void findPathRecursive(TreeNode* node, int targetSum, 
                          vector<int>& currentPath, 
                          vector<vector<int>>& result) {
        if (node == nullptr) return;
        
        // 添加当前节点到路径
        currentPath.push_back(node->val);
        targetSum -= node->val;
        
        // 如果是叶子节点且路径和等于目标值，保存路径
        if (node->left == nullptr && node->right == nullptr && targetSum == 0) {
            result.push_back(currentPath);
        }
        
        // 递归遍历左右子树
        findPathRecursive(node->left, targetSum, currentPath, result);
        findPathRecursive(node->right, targetSum, currentPath, result);
        
        // 回溯，移除当前节点
        currentPath.pop_back();
    }
};

// 辅助函数：创建测试树1
TreeNode* createTestTree1() {
    //       5
    //      / \
    //     4   8
    //    /   / \
    //   11  13  4
    //  /  \      \
    // 7    2      1
    TreeNode* root = new TreeNode(5);
    root->left = new TreeNode(4);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(11);
    root->right->left = new TreeNode(13);
    root->right->right = new TreeNode(4);
    root->left->left->left = new TreeNode(7);
    root->left->left->right = new TreeNode(2);
    root->right->right->right = new TreeNode(1);
    return root;
}

// 辅助函数：创建测试树2
TreeNode* createTestTree2() {
    //   1
    //  / \
    // 2   3
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    return root;
}

// 打印结果
void printPaths(const vector<vector<int>>& paths, int targetSum) {
    cout << "查找和为 " << targetSum << " 的所有路径：" << endl;
    if (paths.empty()) {
        cout << "未找到符合条件的路径" << endl;
        return;
    }
    
    for (const auto& path : paths) {
        cout << "路径: ";
        for (size_t i = 0; i < path.size(); i++) {
            cout << path[i];
            if (i < path.size() - 1) {
                cout << " -> ";
            }
        }
        cout << endl;
    }
}

// 测试函数
void testBinaryTreePaths() {
    cout << "=== C++测试 ===" << endl;
    Solution solution;
    
    // 测试1
    cout << "\n测试1：" << endl;
    TreeNode* root1 = createTestTree1();
    vector<vector<int>> result1 = solution.findPaths(root1, 22);
    printPaths(result1, 22);
    
    // 测试2
    cout << "\n测试2：" << endl;
    vector<vector<int>> result2 = solution.findPaths(root1, 18);
    printPaths(result2, 18);
    
    // 测试3
    cout << "\n测试3：" << endl;
    TreeNode* root2 = createTestTree2();
    vector<vector<int>> result3 = solution.findPaths(root2, 5);
    printPaths(result3, 5);
    
    // 测试4
    cout << "\n测试4：" << endl;
    vector<vector<int>> result4 = solution.findPaths(root2, 4);
    printPaths(result4, 4);
    
    // 释放内存
    delete root1->left->left->left;
    delete root1->left->left->right;
    delete root1->left->left;
    delete root1->left;
    delete root1->right->left;
    delete root1->right->right->right;
    delete root1->right->right;
    delete root1->right;
    delete root1;
    
    delete root2->left;
    delete root2->right;
    delete root2;
}

int main() {
    testBinaryTreePaths();
    return 0;
}
